package utils.opt;

 
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
 

import utils.Util;
import utils.exception.CacheNodeException;

import entities.Individual;
import entities.concept.AndConcept;
import entities.concept.Concept;
import entities.concept.DomainConceptEQ;
import entities.concept.ExistsConcept;
import entities.role.Role;
import entities.role.GeneralRolePath;
import entities.vocabulary.KBVocabulary;

/**
 * A cache tree is a tree with degree 2. Every node contains a binary map that maps to:
 * either 1. Special role RID to some concept
 * or 2. some feature to values
 * @author j55wu
 *
 */
public class CacheTree {
	private static HashMap<Individual, CacheTree> cache
		= new HashMap<Individual, CacheTree>();
	private final Individual ind;
	//each root leads a path of nodes (linked list), head has no incoming links
	private HashSet<CacheTreeNode> roots;
	public static boolean UNSOUND_CACHE = true;

	
	public static void addCache(Individual ind, GeneralRolePath grp, Concept con){
		CacheTree tree = null;
		if(cache.containsKey(ind)){
			tree = cache.get(ind);
		}else{
			tree = new CacheTree(ind);
		}
		try {
			tree.insertCacheEntry(ind, grp, con);
		} catch (CacheNodeException e) {
			System.out.println("Cache entry not inserted: "+grp+con);
		}
		cache.put(ind, tree);
	}
	
	public static HashSet<String> findCacheForFeature(Individual ind, GeneralRolePath grp, Role f){
		HashSet<String> ks = new HashSet<String>();
		if(cache.containsKey(ind)){
			CacheTree ctree = cache.get(ind);
			if(grp == null || !grp.hasRoles()){
				//top level role path
				for(CacheTreeNode nd:ctree.roots){
					if(nd.getKVMap()!= null && nd.getKVMap().containsKey(f)){
						for(Object o:nd.getKVMap().get(f)){
							ks.add((String) o);
						}
					}
				}
				return ks;
			}
			ks.addAll(findCacheForFeature(ctree, grp, f));
			//System.err.println("cahce found "+f+", possible values:"+ks.size());
		}
		return ks;
	}
	
	private static HashSet<String> findCacheForFeature(CacheTree ctree, GeneralRolePath rp, Role f){
		HashSet<String> ks = new HashSet<String>();
		for(CacheTreeNode nd:ctree.roots){
			ks.addAll(findCacheForFeature(nd, rp, f));
		}
		return ks;
	}
	
	private static HashSet<String> findCacheForFeature(CacheTreeNode nd, GeneralRolePath grp,  Role f){
		HashSet<String> ks = new HashSet<String>();
		if(!grp.hasRoles()){
			if(UNSOUND_CACHE){
				//any possible values are returned
				if(nd.getKVMap().containsKey(f)){
					for(Object o:nd.getKVMap().get(f)){
						ks.add((String) o);
					}
				}
			}
			return ks;
		}		
		GeneralRolePath myrp = grp.newCopy();
		CacheTreeNode next = nd.getNextNode(myrp.getLastRole());
		if(next != null){
			//remove this role and continue on the next one
			if(UNSOUND_CACHE){
				int rindex = myrp.getLastRoleIndex();
				//Concept rmc = myrp.removeContentToBottom(rindex);
				myrp.removeContentToBottom(rindex);
			}
			
			ks.addAll(findCacheForFeature(next, myrp, f));
		}
		return ks;
	}
	
	public CacheTree(Individual ind){
		this.ind = ind;
		this.roots = new HashSet<CacheTreeNode>();
	}
	
	public HashSet<CacheTreeNode> getRoots(){
		return this.roots;
	}
	
	public void insertCacheEntry(Individual ins, GeneralRolePath rp, Concept c) throws CacheNodeException{
		if(! ins.equals(ind)){
			throw new CacheNodeException("The instance does not match...");
		}
		if(rp == null || !rp.hasRoles() ){
			CacheTreeNode head = new CacheTreeNode(null, null, null, new HashMap<Role, HashSet<Object>>());
			//no roles, just add the concept TODO: what if rp.concept is not null??		
			head.addNodeValue(Util.parseConceptFromGeneralRolePath(rp, c));
			this.roots.add(head);
		}else{
			CacheTreeNode head = samePathFoundFromRoot(rp);
			if(head == null){
				head = new CacheTreeNode(null, null, null, null);
				this.insertCacheEntry(head, rp, c);
				this.roots.add(head);
			}else{
				modifyExistingPath(head, rp, c);
			}
		}
		
	}
	//modify a path that share some prefixing roles
	public void modifyExistingPath(CacheTreeNode head, GeneralRolePath rp, Concept c) throws CacheNodeException{
		if(rp.length() <= 0){
			this.insertCacheEntry(head, rp, c);
			if(head.getIncomingRole() == null){
				this.roots.add(head);
			}
			return;
		}
		GeneralRolePath myrp = rp.newCopy();
		Role r = myrp.getOldestRole();
		if(head.hasNextNode(r)){
			//if any concept belongs to the current node
			Concept gen = myrp.removeContentToIndex(myrp.getOldestRoleIndex());
			if(gen != null){
				head.addNodeValue(gen);
			}
			if(head.getNextNode1().getIncomingRole().equals(r)){
				modifyExistingPath(head.getNextNode1(), myrp, c);
			}else if(head.getNextNode2().getIncomingRole().equals(r)){
				modifyExistingPath(head.getNextNode2(), myrp, c);
			}else{
				throw new CacheNodeException("No path found for this role:" +r);
			}
		}else{
			this.insertCacheEntry(head, myrp, c);
			if(head.getIncomingRole() == null){
				this.roots.add(head);
			}
		}
		
	}
	
	//test if the most recent role (not necessarily the bottom one) is seen on some path
	public CacheTreeNode samePathFoundFromRoot(GeneralRolePath rp) throws CacheNodeException{
		Role r =  rp.getOldestRole();
		for(CacheTreeNode nd:this.roots){
			if(nd.hasNextNode(r)){
				return nd;
			}	
		}
		return null;
	}
	
	
	private void insertCacheEntry(CacheTreeNode start, GeneralRolePath rp, Concept c) throws CacheNodeException{
		Concept ec = utils.Util.parseConceptFromGeneralRolePath(rp, c);
		//add roles in sequence
		start.addNodeValue(ec);
	}
	
	
}



/**
 * A node has two pointers, as said above.
 * A node value can be:
 * Id->concepts; or F->Strings; or null;
 * Null value means this node has subnodes.
 * Leaf nodes are concept nodes, while intermediate nodes are null nodes.
 * @author j55wu
 *
 */
class CacheTreeNode{
	//at most two next nodes: some R.C and some S.D
	private CacheTreeNode nextNode1;
	private CacheTreeNode nextNode2;
	private final Role incomeRole;
	private HashMap<Role, HashSet<Object>> nodemap; 
	
	public CacheTreeNode(CacheTreeNode next1, CacheTreeNode next2, Role link, HashMap<Role, HashSet<Object>> values){
		this.nextNode1 = next1;
		this.nextNode2 = next2;
		this.incomeRole = link;
		this.nodemap = values;
	}
	
	public Role getIncomingRole(){
		return this.incomeRole;
	}
 
	public CacheTreeNode getNextNode1(){
		return this.nextNode1;
	}
	
	public CacheTreeNode getNextNode2(){
		return this.nextNode2;
	}
	
	//a leaf node has only a map of value, no pointers
	public static CacheTreeNode newLeafCacheTreeNode(Role link){
		return new CacheTreeNode(null, null, link, new HashMap<Role, HashSet<Object>>());
	}
	
	public void setNextNode1(CacheTreeNode next){
		this.nextNode1 = next;
	}
	
	public void setNextNode2(CacheTreeNode next){
		this.nextNode2 = next;
	}

	public void addNodeValue(Concept c) throws CacheNodeException{
		if(c instanceof DomainConceptEQ<?,?>){
			DomainConceptEQ<?,?> dc = (DomainConceptEQ<?,?>) c;
			Role f = (Role) dc.getRealFeature();
			String k = (String) dc.getRealValue();
			this.addToNodeMap(f, k);
		} else if(c instanceof AndConcept){
			//add as ID -> C, decomposing AndConcepts as well
			if(! CacheTree.UNSOUND_CACHE){
				this.addToNodeMap(KBVocabulary.ROLE_ID, c);
			}
			for(Concept ac:((AndConcept)c).getConceptSet()){
				this.addNodeValue(ac);
			}
		}else if(c instanceof ExistsConcept){
			ExistsConcept ec = (ExistsConcept) c;
			Role er = ec.getRole();
			this.addExistsNodeValue(this, er, ec.getFiller());
			
		}else{
			this.addToNodeMap(KBVocabulary.ROLE_ID, c);
		}
	}
	
	public CacheTreeNode addExistsNodeValue(CacheTreeNode father, Role r, Concept c) throws CacheNodeException{
		CacheTreeNode ret = null;
		if(! father.hasNextNode(r)){
			//create new node
			CacheTreeNode nd = new CacheTreeNode(null, null, r, new HashMap<Role, HashSet<Object>>());
			nd.addNodeValue(c);
			ret = nd;
			if(father.nextNode1 == null){
				father.nextNode1 = nd;
			}else if(father.nextNode2 == null){
				father.nextNode2 = nd;
			}else{
				throw new CacheNodeException("Unable to have three subnodes for this concept: "+c);
			}
		}else if(father.nextNode1!=null && father.nextNode1.incomeRole.equals(r)){
			ret = father.nextNode1;
			father.nextNode1.addNodeValue(c);
		}else if(father.nextNode2!=null && father.nextNode2.incomeRole.equals(r)){
			ret = father.nextNode2;
			father.nextNode2.addNodeValue(c);
		}else {
			throw new CacheNodeException("Both subnodes have this role as label: "+r);
		}
		return ret;
	}
	
	public boolean hasNextNode(Role r) throws CacheNodeException{
		if(this.nextNode1 != null && this.nextNode1.incomeRole.equals(r)){
			//already had this role
			return true;
		}else if(this.nextNode2 != null && this.nextNode2.incomeRole.equals(r)){
			return true;
		}
		return false;
	}
	public HashMap<Role, HashSet<Object>> getKVMap(){
		return this.nodemap;
	}
	
	public CacheTreeNode getNextNode(Role r){
		if(this.nextNode1 != null && this.nextNode1.incomeRole.equals(r)){
			return this.nextNode1;
		}else
		if(this.nextNode2 != null && this.nextNode2.incomeRole.equals(r)){
			return this.nextNode2;
		}
		return null;
	}
	
//add: ID -> C or f->k
	private void addToNodeMap(Role r, Object o){
		if(this.nodemap == null){
			this.nodemap = new HashMap<Role, HashSet<Object>>();
		}
		HashSet<Object> values = null;
		if(this.nodemap.containsKey(r)){
			values = this.nodemap.get(r);
		}else{
			values = new HashSet<Object>(); 
		}
		if(o!=null && o instanceof Concept){
			values.add((Concept)o);
		}else if(o != null && o instanceof String){
			values.add((String)o);
		}
		this.nodemap.put(r, values);
	}
		
	public static String displayTree(CacheTreeNode head, int i){
		String out = "";
		for(int j=i; j>0; j--){
			out += "--";
		}
		if(head.getIncomingRole() != null){
			out += head.getIncomingRole()+"***";
		}else{
			out+="HEAD\n";
		}
		i++;
		if(head.nodemap != null){
			for(Entry<Role, HashSet<Object>> e:head.nodemap.entrySet()){
				out+= e.getKey().toString()+"->(";
				for(Object o:e.getValue()){
					out += o.toString()+",";
				}
				out +="); ";
			}
			out+="\n";
		}
		
		if(head.getNextNode1()!=null){
			out += "L: "+displayTree(head.getNextNode1(), i);
		}
		if(head.getNextNode2()!=null){
			out += "R: "+displayTree(head.getNextNode2(), i);
		}
		return out;
	}
	@Override
	public String toString(){
		String st = this.hashCode()+ ": ";
		st += " <--- "+this.incomeRole+".{";
		if(this.nodemap == null){
			st += "}";
		}else{
			for(Entry<Role, HashSet<Object>> e:this.nodemap.entrySet()){
				st+= e.getKey().toString()+"->(";
				for(Object o:e.getValue()){
					st += o.toString()+",";
				}
				st+="); ";
			}
			st+="}";
		}
		
//		if(this.nextNode1 != null){
//			st+="\n"+ this.hashCode() +" left -- " + this.nextNode1.toString();
//		}
//		if(this.nextNode2 != null){
//			st+="\n"+ this.hashCode() +" right -- " + this.nextNode2.toString();
//		}
		return st;
	}

	
}